package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	array := []int{}
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	for i := 0; i < 100000; i++ {
		array = append(array, r.Intn(1000))
	}
	fmt.Println("start sort......")
	startTime := time.Now()
	array = sort(array)
	endTime := time.Now()
	//fmt.Println(array)
	fmt.Printf("Time spent: %v", endTime.Sub(startTime))
}

func sort(array []int) []int {
	if len(array) <= 1 {
		return array
	} else if len(array) == 2 {
		if array[0] > array[1] {
			array[0], array[1] = array[1], array[0]
		}
		return array
	} else {
		base := array[0]
		left := 0
		right := len(array) - 1
		checkFinish := func() bool {
			return left == right
		}
		leftSearch := func() {
			for {
				if left >= right {
					break
				}
				temp := array[left]
				if temp > base {
					array[right] = temp
					break
				}
				left++
			}
		}
		rightSearch := func() {
			for {
				if right <= left {
					break
				}
				temp := array[right]
				if temp < base {
					array[left] = temp
					break
				}
				right--
			}
		}
		for {
			rightSearch()
			leftSearch()
			if checkFinish() {
				break
			}
		}
		leftArray := sort(array[0:left])
		rightArray := sort(array[left+1:])
		leftArray = append(leftArray, base)
		leftArray = append(leftArray, rightArray...)
		return leftArray
	}
}
